package find.longest.substring;

import java.util.HashMap;
import java.util.Map;

/**
 * @Time 2020/1/2
 * @author 王光浩
 * @Need 给出一个字符串，获得其中最长但不包含重复字符的字符串的长度。
 * @Thinking 使用HashMap。key为字符，value为对应下标。
 *           思路：遍历一遍字符串，设置一个maxLen——保存符合要求的最大字符串长度，设置一个presentLen——保存当前子字符串
 *                 长度，设置一个firstIndex——保存当前子字符串的首字符下标，遍历过程中，如果待加入的字符不存在与HashMap
 *                 中，则将其加入HashMap中并将presentLen++，否则比较presentLen和maxLen的大小判断是否更新maxLen，然后
 *                 将present=0，然后更新firstIndex=重复字符的value+1，然后更新重复字符的value为当前i（如果重复字符的
 *                 value<firstIndex，则仅仅更新重复字符的value值，不做其他任何相关操作）。
 *           复杂度分析：时间复杂度O（n），空间复杂度O（n），n为字符串长度。
 *           简化：不需要presentLen，因为我们已经有了最小有效字符下标，可以使用i-有效字符下标+1，代替presentLen
 */
public class MyMethodTwo {
    public int lengthOfLongestSubstring(String s) {
    	Map<Character,Integer> hashMap=new HashMap<Character,Integer>();
    	//初始化数据
    	int maxLen=0;
    	int previous=0;
    	int firstIndex=0;
    	int sLen=s.length();
    	//求出符合要求的最长子字符串长度
    	for(int i=0;i<sLen;i++) {
    		if(hashMap.containsKey(s.charAt(i))) {
    			if(hashMap.get(s.charAt(i))>=firstIndex) {   
    				previous=i-firstIndex;                   //获取子字符串长度（i-首下标）
    				maxLen=(maxLen>previous?maxLen:previous); 
    				firstIndex=hashMap.get(s.charAt(i))+1;      //更新有效最小下标
    			}
    		}
    		hashMap.put(s.charAt(i), i);  //存在则更新，否则添加
    	}
    	previous=sLen-firstIndex;   //最后一个字符串的长度       
    	//返回最长的一个
    	return maxLen>previous?maxLen:previous;
    }
}
